Masala #1156

Xotira 256 MB Vaqt 3000 ms Qiyinchiligi 40 %
14

  

Robolandiya poyezdlari

Robolandiya mamlakatida \(N\) ta shahar mavjud. Har bir shahar ketma-ket joylashgan va har biri tartib bilan raqamlangan. Bundan tashqari, ushbu shaharlar orasida qatnovchi \(M\) ta poyezd bor. \(i-\)poyezd \(L_i\) - \(R_i\) shaharlari orasida qatnaydi \((1 \le L_i \le R_i \le N)\).

Robolandiya qiroli ushbu poyezdlarga qiziqib qoldi va endi u vazirlaridan so'ramoqda: ″\(p_i\) va \(q_i\) shaharlari orasida qatnovchi nechta poyezd bor?″.

Sizning vazifangiz quyidagi shartni qanoatlantiruvchi poyezdlar sonini topishdir.

\(p_i \le L_j \le R_j \le q_i\).


Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida uchta butun son - N, M, Q - shaharlar, poyezdlar va so'rovlar soni \((1 \le N \le 500, 1 \le M , Q \le 2*10^6)\).

Keyingi M ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(L_i\) va \(R_i\) mavjud.

Keyingi Q ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(p_i\) va \(q_i\) mavjud.


Chiquvchi ma'lumotlar:

Chiqish faylining Q ta qatorida, har bir so'rov uchun ushbu oraliqda harakatlanuvchi poyezdlar sonini chop eting.


Misollar
# input.txt output.txt
1
2 3 1
1 1
1 2
2 2
1 2
3
2
5 10 5
3 4
1 4
1 2
1 1
2 5
2 5
1 2
1 3
3 5
3 4
1 2
1 1
5 5
1 5
2 4
3
1
0
10
2
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin